package com.kk.datastructure.sort;

import java.text.SimpleDateFormat;
import java.util.Arrays;
import java.util.Date;

/**
 * title: 冒泡排序+优化
 * @author 阿K
 * 2020年12月6日 下午9:08:11 
 */
public class BubbleSort {

	public static void main(String[] args) {	
		// int arr[] = {3, 9, -1, 10, 20};
		// new BubbleSort(arr);
		// System.out.println(Arrays.toString(arr));
		
		// 测试一下冒泡排序的速度O(n^2), 给80000个数据，测试
		// 创建要给80000个的随机的数组
		int[] arr = new int[80000];
		for(int i =0; i < 80000;i++) {
			arr[i] = (int)(Math.random() * 8000000); //生成一个[0, 8000000) 数
		}
		new BubbleSort(arr);
	}
	
	
	SimpleDateFormat simpleDateFormat = new SimpleDateFormat("yyyy-MM-dd HH:mm:ss");
	// 策略模式
	public BubbleSort(int[] arr) {
		long time = new Date().getTime();
		bubbleSort(arr);
		long time2 = new Date().getTime();
		System.out.println("使用了："+(time2-time)+"毫秒");
	}
	
	// 冒泡排序  Api
	private static void bubbleSort(int[] arr) {
		int temp = 0;// 用于交换的临时变量 
		boolean flag = false;// 用于标识，是否交换过 
		// 冒泡排序 的时间复杂度 O(n^2),因为套了两个循环
		for (int i = 0; i < arr.length - 1; i++) {
			for (int j = 0; j < arr.length- 1 -i; j++) {
				// 如果前面的数比后面的数大，则交换
				if(arr[j]>arr[j+1]) {
					flag = true;
					temp = arr[j];
					arr[j] = arr[j+1];
					arr[j+1]= temp;
				}
			}
			if(!flag) {
				// 在一趟排序中，一次交换都没有发生过,或者是一大轮已经排了一次
				break;// 无序继续操作
			}else {
				flag = false;// 重置flag!!!, 进行下次判断
			}
		}
	}
}
